﻿/* Write a program that finds the index of given element in a sorted array of integers 
 * by using the binary search algorithm (find it in Wikipedia). */



using System;
using System.Diagnostics;

class IndexBinarySearch
{
    static void Main()
    {
        uint N;
        int E;
        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);
        
        iProvided = false; //reset iProvided
        
        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do
            {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i + 1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }

        iProvided = false; //reset iProvided

        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter a valid integer number.");
            else iProvided = true;
            Console.Write("Element to search for: ");
        } while (Int32.TryParse(Console.ReadLine(), out E) == false);
        
        //clone the array
        int[] sortedNums = (int[])nums.Clone();
        
        //sort the array
        Array.Sort(sortedNums);
        
        //output sorted array
        Console.WriteLine("Sorted: ");
        Console.WriteLine(string.Join(", ", (int[])sortedNums.Clone()));

        //where we store the index found
        //int? index = Array.BinarySearch(sortedNums, E);
        int? index = Binary_Search(sortedNums, E, 0, nums.Length-1);

        if (index >= 0)
        {
            Console.WriteLine("{0} was found in the sorted array on position with index {1}", E, index);
        }
        else Console.WriteLine("No occurrances of {0} were met", E);

        Console.WriteLine();    

    }

    /* method to find the index of given element in a sorted array using the binary search algorithm
     * using Deferred detection of equality
     */
    private static int Binary_Search(int[] A, int key, int imin, int imax)
    {
        // continually narrow search until just one element remains
        while (imin < imax)
        {
            int imid = (imin + imax) >> 1;

            // code must guarantee the interval is reduced at each iteration
            Debug.Assert(imid < imax);
            // note: 0 <= imin < imax implies imid will always be less than imax

            // reduce the search
            if (A[imid] < key)
                imin = imid + 1;
            else
                imax = imid;
        }
        // At exit of while:
        //   if A[] is empty, then imax < imin
        //   otherwise imax == imin

        // deferred test for equality
        if ((imax == imin) && (A[imin] == key))
            return imin;
        else
            return -1; //return negative value, nothing was found
    }
}
